package com.zhanghp.class06;

import com.zhanghp.refer.TreeNode;

/**
 * <h1>平衡二叉树</h1>
 * <p>
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 * </p>
 * <p>
 * 本题中，一棵高度平衡二叉树定义为：
 * <br/>
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * </p>
 * <a href="https://leetcode.cn/problems/balanced-binary-tree">leetcode</a>
 * <p>举例</p>
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * <br/>
 * 输出：true
 * </p>
 *
 * @author zhp
 * @since 2024/1/22 17:47
 */
public class Code02_IsBalancedBinaryTree {

    public boolean isBalanced(TreeNode root) {
        return process(root).isBalance();
    }

    private TreeInfo process(TreeNode root) {
        if (root == null) {
            return new TreeInfo(0, true);
        }
        TreeInfo left = process(root.left);
        TreeInfo right = process(root.right);
        // 左树是否平衡 && 右树是否平衡 && 左右树高度相减的绝对值是否小于2
        boolean balance = left.balance && right.balance && Math.abs(left.height - right.height) < 2;
        // 取最大 + 本root
        int height = Math.max(left.height, right.height) + 1;
        return new TreeInfo(height, balance);
    }

    public static class TreeInfo {

        /**
         * 当前树深度
         */
        public int height;

        /**
         * 当前树是否是平衡树
         */
        public boolean balance;

        public TreeInfo(int height, boolean balance) {
            this.height = height;
            this.balance = balance;
        }

        public boolean isBalance() {
            return balance;
        }
    }
}
